package com.demo.java.OD201_250.OD236;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【基站维修工程师】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145933741
 */
public class OdMain {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(reader.readLine());

        int[][] arr = new int[num][num];
        for (int i = 0; i < num; i++) {
            String[] tokens = reader.readLine().split(" ");
            for (int j = 0; j < num; j++) {
                arr[i][j] = Integer.parseInt(tokens[j]);
            }
        }

        boolean[] visited = new boolean[num];
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < num; i++) {
            visited[i] = true;
            int temp = dfs(arr, visited, i, arr[0][i], 1);
            visited[i] = false;
            min = Math.min(temp, min);
        }

        System.out.println(min);
    }

    // DFS 算法，遍历所有基站的路径
    public static int dfs(int[][] arr, boolean[] visited, int curIndex, int len, int count) {
        visited[curIndex] = true;

        // 如果已经遍历了所有基站，返回当前路径的长度加上从当前基站返回到起点的距离
        if (count == visited.length - 1) {
            visited[curIndex] = false;
            return len + arr[curIndex][0];
        }

        int min = Integer.MAX_VALUE;
        // 遍历所有未访问的基站
        for (int i = 1; i < arr.length; i++) {
            if (!visited[i]) {
                min = Math.min(min, dfs(arr, visited, i, len + arr[curIndex][i], count + 1));
            }
        }

        visited[curIndex] = false;
        return min;
    }
}